package leetcode.hot100;
import java.util.HashMap;

public class Solution76 {

    public static void main(String[] args) {
        String s = "ADOBECODEBANC", t = "ABC";
        System.out.println(new Solution76().minWindow(s,t));
    }

    public String minWindow(String s, String t) {
        int minLen = s.length() + 1, start = 0; //记录结果的长度以及起始位置
        HashMap<Character,Integer> missingNum = new HashMap<>(); //当前子字符串相比t每种字符缺失的次数
        int missingType = 0; //当前子字符串相比t缺失字符的种类数
        for (int i = 0; i < t.length(); i++) {
            //如果当前字符是第一次统计，missingType++
            if(!missingNum.containsKey(t.charAt(i))){
                missingType++;
                missingNum.put(t.charAt(i),1);
            }else {
                missingNum.put(t.charAt(i),missingNum.get(t.charAt(i))+1);
            }
        }
        int left = 0, right = 0;
        while (right < s.length()) { //扩张窗口，内部看情况收缩窗口
            String subString = s.substring(left,right+1);
            if (missingNum.containsKey(s.charAt(right))) {
                missingNum.put(s.charAt(right),missingNum.get(s.charAt(right))-1);
                //如果缺失的这种字符都补齐了，就把缺失种类减掉1
                if (missingNum.get(s.charAt(right)) == 0) missingType--;
            }
            //如果所有缺失字符都补齐了，就对当前字符串左边进行收缩,直到子字符串不能覆盖t
            while (missingType == 0) {
                //收缩之前先做一些值的更新
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }
                if (missingNum.containsKey(s.charAt(left))){
                    missingNum.put(s.charAt(left),missingNum.get(s.charAt(left))+1);
                    //收缩之前不缺，现在这种字符又缺了
                    if(missingNum.get(s.charAt(left))>0) missingType++;
                }
                //进行收缩
                left++;
            }
            right++;
        }
        return minLen>s.length()?"":s.substring(start,start+minLen);
    }
}
